package leetcode_300;

import java.util.LinkedList;
import java.util.Queue;

/**
 *@author 周杨
 *UglyNumberII_264_  输出第n个uglyNumber
 *describe:筛选法 每次只生成uglyNumber 维护三个队列  AC 19%  可以优化 用数组当三个队列
 *2018年6月26日 上午10:47:45
 */
public class UglyNumberII_264_ {

	public static void main(String[] args) {
		UglyNumberII_264_ test=new UglyNumberII_264_();
		System.out.println(test.nthUglyNumber(10));

	}
	
	/**
	 * describe:筛选法 每次只生成uglyNumber 维护三个队列 
	 * 2018年6月26日 上午10:47:07
	 */
	public int nthUglyNumber(int n) {
		 if(n==1)
				return 1;
	     Queue<Integer> l2=new LinkedList<Integer>();
	     Queue<Integer> l3=new LinkedList<Integer>();
	     Queue<Integer> l5=new LinkedList<Integer>();
	     int count=1;
	     l2.add(2);
	     l3.add(3);
	     l5.add(5);
	     while(count<n) {
	    	 int min=Math.min(Math.min(l2.peek(), l3.peek()), l5.peek());
	    	 if(count==n-1)
	    		 return min;
	    	 if(l2.peek()==min) {
	    		 l2.poll();
	    	 }
	    	 if(l3.peek()==min)
	    		 l3.poll();
	    	 if(l5.peek()==min)
	    		 l5.poll();
	    	 l2.add(min*2);
	    	 l3.add(min*3);
	    	 l5.add(min*5);
	    	 ++count;
	     }
	     return -1;
	}
	
	/**
	 * describe:穷举法超时
	 * 2018年6月26日 上午10:28:57
	 */
	public int nthUglyNumber1(int n) {
       int count=0;
       for(int i=1;i<=Integer.MAX_VALUE;++i) {
    	   if(isUgly(i))
    		   if(count==n-1)
    			   return i;
    		   else
    	   		++count; 
       }
        return -1;
    }
	
	public boolean isUgly(int num) {
		 if(num==1) return true;
	        if(num==0) return false;
	        while(num%2==0) num=num/2;
	        while(num%3==0) num=num/3;
	        while(num%5==0) num=num/5;
	        return num==1;
	}
	
	/**
	 * describe:AC 95%
	 * 2018年6月26日 上午10:49:27
	 */
	public int nthUglyNumber2(int n) {
        int[] nums = new int[n];
        nums[0] = 1;
        //p2 p3 p5只存出现多少对应的数  同理乘以2 3 5就是当前候选数
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;
        for (int i = 1; i < n; i++) {
            nums[i] = Math.min(nums[p2] * 2, Math.min(nums[p3] * 3, nums[p5] * 5));
            //判断刚才的数存到哪个队列里了
            if (nums[i] == nums[p2] * 2) p2++;
            if (nums[i] == nums[p3] * 3) p3++;
            if (nums[i] == nums[p5] * 5) p5++;
        }
        
        return nums[n - 1];
    }
}
